package com.sub.structure;

/**
 * @ClassName SubDynamicArray
 * @Description: 数组的特点：连续的内存空间，随机访问，存储相同类型的数据，查询快，插入删除慢（插入和删除可能需要移动其它元素，开销大）
 *  * 逻辑结构：数组（Array）是一个线性结构，其由一系列元素组成。每个元素都有一个索引（index）,索引从0开始。可以根据索引获取数组中的任意元素。
 *  * 物理结构：数组中的元素存储在内存中一段连续的空间中，通常将这段空间的起始位置作为整个数组的位置标识
 * 数组这一数据结构的一个局限性是长度固定，如下实现一个增强版的数组——可变长的动态数组
 * 需求：初始化容量为16，当数组满时，扩容为原来的2倍，保证连续？（数组扩容后，地址会发生变化，需要将原数组的元素拷贝到新数组中）
 * 方法	功能说明
 * int size()	返回动态数组中当前元素的个数
 * boolean isEmpty()	判断动态数组是否为空
 * add(int index, E element)	在指定位置插入新元素
 * add(E element)	在末尾插入新元素
 * E get(int index)	获取指定位置的元素
 * E remove(int index)	删除指定位置的元素，并返回删除内容
 * E set(int index, E element)	修改指定位置的元素
 * forEach(Consumer<E> consumer)	遍历数组元素
 * @Author Submerge.
 * @Since 2025/5/15 17:00
 * @Version 1.0
 */
public class SubDynamicArray<E> {

    //数组元素容器（还是数组）
    private Object[] elementData;

    //数组初始长度
    private static final int INITIAL_CAPACITY = 16;

    //扩容因子
    private static final int GROWTH_FACTOR = 2;


    //数据长度
    private int size;


    /**
     * 默认构造：初始化动态数组，默认容量为16
     */
    public SubDynamicArray() {
        this.elementData = new Object[INITIAL_CAPACITY];
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 在指定位置插入新元素：插入的元素不能越界
     *
     * @param index   插入位置
     * @param element 插入的元素
     */
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (size >= elementData.length) {
            // 容量不足则扩容
            grow();
        }
        //将index位置及之后的元素向后移动一位
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        //插入新元素
        elementData[index] = element;
        size++;
    }

    /**
     * 扩容
     */
    private void grow() {
        int newCapacity = elementData.length * GROWTH_FACTOR;
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(elementData, 0, newArray, 0, size);
        elementData = newArray;
    }

    /**
     * 在末尾插入新元素
     *
     * @param element 插入的元素
     */
    public void add(E element) {
        if (size >= elementData.length) {
            grow();
        }
        elementData[size++] = element;
    }

    /**
     * 获取指定位置的元素
     *
     * @param index 索引
     * @return 返回指定位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (E) elementData[index];
    }

    /**
     * 删除指定位置的元素
     *
     * @param index 索引
     * @return 返回删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        E oldValue = (E) elementData[index];
        // 要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null; // 清除最后一个元素
        return oldValue;
    }

    /**
     * 修改指定位置的元素
     *
     * @param index   索引
     * @param element 新元素
     * @return 返回旧元素
     */
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    /**
     * 遍历数组元素
     * @param consumer 消费者函数
     */
    public void forEach(java.util.function.Consumer<E> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept((E) elementData[i]);
        }
    }


    /**
     * 重写toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("SubDynamicArray{");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
    }


}
